package 中等.动态规划.背包;

/**
 * 给你两个 正 整数 n 和 x 。
 * 请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，
 * 你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1x + n2x + ... + nkx 。
 * 由于答案可能非常大，请你将它对 109 + 7 取余后返回。
 * 比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 23 + 33 + 53 。
 *
 * @ https://leetcode.cn/problems/ways-to-express-an-integer-as-sum-of-powers/description/
 * @date 2024/09/08
 */
public class 将一个数字表示成幂的和的方案数_2787 {

    public static void main(String[] args) {

        System.out.println(numberOfWays(4, 1));

    }

    /**
     * 0-1 背包
     * n 最大为 300，从 1 的 x 次幂开始选或者不选
     * 1，子问题
     * dp[i][j] 表示从 [0,i-1] 中选取某几个元素，和为 j 的方案数是 dp[i][j]
     */
    public static int numberOfWays(int n, int x) {
        long[][] dp = new long[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int pow = (int) Math.pow(i, x);
                // 不选
                dp[i][j] += dp[i - 1][j];
                dp[i][j] %= 1000000007;
                if (j < pow) {
                    continue;
                }
                // 选
                if (j == pow) {
                    // 一个数子的x次幂，正好是背包容量，方案+1
                    dp[i][j]++;
                } else {
                    dp[i][j] += dp[i - 1][j - pow];
                    dp[i][j] %= 1000000007;
                }
            }
        }

        return (int) dp[n][n];
    }

}
